//
//  MinDepth.swift
//  LeetCodeDemo
//
//  Created by Yangdongwu on 2020/12/19.
//

import Foundation

class MinDepth {
    
    func minDepth(_ root: TreeNode?) -> Int {
        // 如果为空那么最小深度就是 0
        guard let root = root else {
            return 0
        }
        // 如果左子树右子树为空 最小深度就是 1
        if root.left == nil && root.right == nil {
            return 1
        }
        // 取一个最大值
        var minD = Int.max
        // 递归求左子树最小深度
        if root.left != nil {
            minD = min(minDepth(root.left), minD)
        }
        // 递归求右子树的最小深度
        if root.right != nil {
            minD = min(minDepth(root.right), minD)
        }
        // 结果为左子树和右子树的最小深度 + 1
        return minD + 1
    }
    
    func minDepth10(_ root: TreeNode?) -> Int {
        guard let root = root else {
            return 0
        }
        let left = minDepth(root.left)
        let right = minDepth(root.right)
        //如果有一边为空 就算另一边的最小深度 + 1
        if left == 0 || right == 0 {
            return left + right + 1
        }
        // 否则就是求两边中的最小深度 + 1
        return min(left, right) + 1
    }
    
}
